import java.util.*;

class ListNode{
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) { return ;}

        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode head2 = new ListNode(-1);
        ListNode cur  = slow.next;
        slow.next = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = tmp;
        }

        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(-1);
        ListNode prev = ret;
        while(cur1 != null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            if(cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        for(ListNode x : lists){
            if(x != null){
                heap.offer(x);
            }
        }

        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        while(!heap.isEmpty()){
            ListNode tmp = heap.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null) { heap.offer(tmp.next);}
        }
        return ret.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int left, int right){
        if(left > right) { return null;}
        if(left == right) { return lists[left];}

        int mid = (left + right) / 2;
        ListNode l = merge(lists, left, mid);
        ListNode r = merge(lists, mid + 1, right);
        return mergeTwo(l, r);
    }
    public ListNode mergeTwo(ListNode l1, ListNode l2){
        if(l1 == null) { return l2;}
        if(l2 == null) { return l1;}

        ListNode ret = new ListNode(-1);
        ListNode cur1 = l1, cur2 = l2, prev = ret;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) { prev.next = cur1;}
        if(cur2 != null) { prev.next = cur2;}
        return ret.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while(cur != null){
            cur = cur.next;
            n++;
        }
        n /= k;

        ListNode newHead = new ListNode(-1);
        ListNode prev = newHead;
        cur = head;
        for(int i = 0; i < n; i++){
            ListNode tmp = cur;
            for(int j = 0; j < k; j++){
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }

        prev.next = cur;
        return newHead.next;
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int x = target - nums[i];
            if(map.containsKey(x)){
                return new int[]{i, map.get(x)};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1,-1};
    }

    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) { return false;}
        int[] hash = new int[26];
        for(int i = 0; i < s1.length(); i++){
            hash[s1.charAt(i) - 'a']++;
        }

        for(int i = 0; i < s2.length(); i++){
            hash[s2.charAt(i) - 'a']--;
            if(hash[s2.charAt(i) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
}
